//给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选
//择一个符号添加在前面。 
//
// 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。 
//
// 
//
// 示例： 
//
// 输入：nums: [1, 1, 1, 1, 1], S: 3
//输出：5
//解释：
//
//-1+1+1+1+1 = 3
//+1-1+1+1+1 = 3
//+1+1-1+1+1 = 3
//+1+1+1-1+1 = 3
//+1+1+1+1-1 = 3
//
//一共有5种方法让最终目标和为3。
// 
//
// 
//
// 提示： 
//
// 
// 数组非空，且长度不会超过 20 。 
// 初始的数组的和不会超过 1000 。 
// 保证返回的最终结果能被 32 位整数存下。 
// 
// Related Topics 深度优先搜索 动态规划 
// 👍 496 👎 0


package com.yun.leetcode.editor.cn;

import java.util.HashMap;

public class TargetSum {
    public static void main(String[] args) {
        Solution solution = new TargetSum().new Solution();
        System.out.println(solution.findTargetSumWays(new int[]{1, 1, 1, 1, 1}, 3));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
//
//        public int findTargetSumWays(int[] nums, int S) {
//            int[][] dp = new int[nums.length + 1][nums.length + 1];
//            // 0, 0 是起点，然后x代表加，y代表减
//            for (int i = 0; i < nums.length; i++) {
//                for (int j = 0; j < nums.length; j++) {
//                    int num = nums[0];
//                    dp[i + 1][j] = dp[i][j] + num;
//                    dp[i][j + 1] = dp[i][j] - num;
//                }
//            }
//            return 0;
//        }


        // 备忘录map： 当前i索引，当前位置的加的结果 => 次数【得出结果的方式】
        int findTargetSumWays(int[] nums, int target) {
            // 备忘录,直接粘贴过来的代码
            // 要用备忘录，一定要抽象出方法。
            // 直接用第一版的回溯法，计算的sum和size都是类变量，这个不好加起来。
            if (nums.length == 0) return 0;
            return dp(nums, 0, target);
        }

        // 备忘录
        HashMap<String, Integer> memo = new HashMap<>();
        int dp(int[] nums, int i, int rest) {
            // base case
            if (i == nums.length) {
                if (rest == 0) return 1;
                return 0;
            }
            // 把它俩转成字符串才能作为哈希表的键
            String key = i + "," + rest;
            // 避免重复计算
            if (memo.containsKey(key)) {
                return memo.get(key);
            }
            // 还是穷举
            int result = dp(nums, i + 1, rest - nums[i]) + dp(nums, i + 1, rest + nums[i]);
            // 记入备忘录
            memo.put(key, result);
            return result;
        }

        // --------------------------------------------------
//        public int findTargetSumWays(int[] nums, int S) {
////        int sum = 0;
////        // 画一下递归树，先写出暴力解法
////        for (int num : nums) {
////            // 对于每个num，有加和减两种方式。
////            // 回溯算法的框架，
////            // 做选择，撤销选择。
////        }
//
//            trackBack(nums, 0, S);
//            return size;
//
//        }
//
//        private int size;
//        private int sum;
//
//        private void trackBack(int[] nums, int cur, int target) {
//            if (cur == nums.length) {
//                if (sum == target) {
//                    size++;
//                }
////                System.out.println();
//                return;
//            }
//            int num = nums[cur];
//            // 有加和减两种选择。
//            sum += num;
//            trackBack(nums, cur + 1, target);
//            sum -= num;
//            sum -= num;
//
//            trackBack(nums, cur + 1, target);
//
//            sum += num;
//        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}